#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

class Solution{
private:
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs){
        vector<vector<string>> ans;
        map<string,vector<string>> map_ans;
        for(int i=0;i<strs.size();i++){
            string key = strs[i];
            sort(key.begin(),key.end());
            auto iter = map_ans.find(key);
            if(iter == map_ans.end()){
                vector<string> tmp = {strs[i]};
                map_ans.insert(pair<string,vector<string>>(key,tmp));
            }
            else{
                vector<string> tmp = map_ans[key];
                tmp.push_back(strs[i]);
                auto iter = map_ans.find(key);
                iter->second = tmp;
            }
        }   
        for(auto iter=map_ans.begin();iter!=map_ans.end();iter++){
            ans.push_back(iter->second);
        }
        return ans;
    }
};


int main(){
    Solution solu = Solution();
    vector<string> input = {"eat", "tea", "tan", "ate", "nat", "bat"};
    solu.groupAnagrams(input);
    int i = 1;
    return 0;
}
